struct TrieNode {
    children: [Option<Box<TrieNode>>; 256],
    data: Option<i32>,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: [None; 256],
            data: None,
        }
    }
}

struct Trie {
    root: Box<TrieNode>,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: Box::new(TrieNode::new()),
        }
    }

    fn insert(&mut self, key: &str, value: i32) {
        let mut node = &mut self.root;

        for byte in key.bytes() {
            if node.children[byte as usize].is_none() {
                node.children[byte as usize] = Some(Box::new(TrieNode::new()));
            }
            node = node.children[byte as usize].as_mut().unwrap();
        }

        node.data = Some(value);
    }

    fn search(&self, key: &str) -> Option<i32> {
        let mut node = &self.root;

        for byte in key.bytes() {
            if let Some(child) = &node.children[byte as usize] {
                node = child;
            } else {
                return None;
            }
        }

        node.data
    }

    fn remove(&mut self, key: &str) -> bool {
        Self::remove_helper(&mut self.root, key.as_bytes(), 0)
    }

    fn remove_helper(node: &mut Box<TrieNode>, key: &[u8], depth: usize) -> bool {
        if depth == key.len() {
            if node.data.is_some() {
                node.data = None;
                return true;
            }
            return false;
        }

        let byte = key[depth];
        if let Some(child) = &mut node.children[byte as usize] {
            if Self::remove_helper(child, key, depth + 1) {
                node.children[byte as usize] = None;

                // Check if the current node should be deleted
                for child in &node.children {
                    if child.is_some() {
                        return false;
                    }
                }

                if node.data.is_none() {
                    return true;
                }
            }
        }

        false
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("hello", 10);
    println!("Found: {:?}", trie.search("hello")); // Should print "Found: Some(10)"
    trie.remove("hello");
    println!("Found: {:?}", trie.search("hello")); // Should print "Found: None"
}
